package 滑动窗口And双指针;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/1/9 13:58
 */
public class leetcode209长度最小的子数组 {

    /*
     先加 后判断
     还是 先判断 后 加
     这真的 还是 一个  ** 坑 ** 点
     */
    // 暴力 O(N ^ 2)
    public int violence(int []nums,int target){
        int len = nums.length;
        int ans = Integer.MAX_VALUE;
        for(int i = 0;i < len; i++){
            int sum = 0;
            for(int j = i + 1;j < len;j++){
                sum += nums[j];
                if(sum >= target){
                    ans = Math.min(ans,j - i + 1);
                    break;
                }
            }
        }
        return ans == Integer.MAX_VALUE ? ans : 0;
    }
    /*
     这个题就有单调性了
     好好体验 一下 这其中 的单调性!
     O(N)
     */
    public int solution(int []nums,int target){
        int len = nums.length;
        int ans = Integer.MAX_VALUE;
        int []preSum = new int[len + 1];
        /*
          preSum[i] = sum[ 0 , i ) , 表示的就是 左闭右开 的一个区间和, 这样会好记一些
          ==============
         */
        for(int i = 0;i < len;i++ ){
            preSum[i + 1]  = preSum[i] + nums[i];
        }
        int left = 0,right = 0;
        // 这里的 left <= right 的判断 也是 很有必要的!
        while(right < len && left <= right){
            if(preSum[right + 1] - preSum[left] >= target){
                // 先 计算 长度 之后, 再让 left ++
                ans = Math.min(ans,right - left++ + 1);
            }
            else{
                right++;
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }



    /*
     错误的原因 :
     sum >= target 这个 判断
     与  sum += nums[right] 的 顺序 不对
     应该 先加 后 判断, 这个 顺序 问题
     ==================
     下面的修正, 是参考 官方题解的 写法!
     个人 还是 比较推荐这种写法的!
     */
    public static int solution1(int []nums,int target){
        int ans = nums.length + 1;
        int sum = 0;
        int left = 0,right = 0;
        while(right < nums.length && left <= right){
            sum += nums[right];
            while(sum >= target){
                ans = Math.min(ans,right - left + 1);
                sum -=nums[left++];
            }
            right++;
        }
        return ans == nums.length + 1 ? 0 : ans;
    }

    public static void main(String[] args) {
//        int [] nums = {2,3,1,2,4,3};
        int [] nums = {1,4,4};
        int target = 4;
        System.out.println(solution1(nums,target));
    }

}
